#define lson l,m,root<<1
#define rson m+1,r,root<<1|1
const int NV = 100005;
int add[NV<<2],sum[NV<<2];
void PushUp(int root)
{
sum[root]=sum[root<<1]+sum[root<<1|1];
}
void PushDown(int root,int m)
{
if (add[root])
{
add[root<<1] += add[root];
add[root<<1|1] += add[root];
sum[root<<1] += add[root] * (m - (m >> 1));
sum[root<<1|1] += add[root] * (m >> 1);
add[root] = 0;
}
}
void build(int l,int r,int root=1)
{
add[root] = 0;
if (l == r)
{
sum[root]=0;
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(root);
}
void update(int Left,int Right,int newvalue,int l,int r,int root=1)
{
if (Left <= l && r <= Right)
{
add[root] += newvalue;
sum[root] += newvalue * (r - l + 1);
return ;
}
PushDown(root , r - l + 1);
int m = (l + r) >> 1;
if (Left <= m) update(Left , Right , newvalue , lson);
if (m < Right) update(Left , Right , newvalue , rson);
PushUp(root);
}
int query(int Left,int Right,int l,int r,int root=1)
{
if (Left <= l && r <= Right)
{
return sum[root];
}
PushDown(root , r - l + 1);
int m = (l + r) >> 1;
int ret = 0;
if (Left <= m) ret += query(Left , Right , lson);
if (m < Right) ret += query(Left , Right , rson);
return ret;
}